package P215.P347;

import org.junit.Test;

import java.util.HashMap;
import java.util.List;

/**
 * @Author DJ同学
 * @Date 2021/3/2 22:18
 * @Version 1.0
 * @Name 前 K 个高频元素
 * @Problem https://leetcode-cn.com/problems/top-k-frequent-elements/
 *
 * 使用堆+headmap
 * 使用小根堆，如果使用小根堆，每次删除最大的 得到的结果就是后k个高频元素
 */
public class Solution {
    @Test
    public void test(){
        int[] ints = topKFrequent(new int[]{1,2}, 2);
        System.out.println("end");
    }

    int[] maxHeap;
    int size = 0;
    HashMap<Integer,Integer> map;
    public int[] topKFrequent(int[] nums, int k) {
        map = new HashMap<>();
        //构造 map[i]++
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        maxHeap = new int[nums.length+1];

        int tempk = k;
        for(Integer key: map.keySet()){
            add(key);//放key
            if(tempk<=0){
                delete();
            }
            tempk--;
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = maxHeap[i+1];
        }
        return res;

    }
    void add(Integer num){
        maxHeap[++size] = num;
        int j = size;
        for(;j>1&&map.get(num)<map.get(maxHeap[j/2]);j/=2){//比较value
            maxHeap[j]=maxHeap[j/2];
        }
        maxHeap[j] = num;
    }
    void delete(){
        int temp = maxHeap[size--];
        int parent = 1;
        int child = 2;
        while(child<=size){
            if(child+1<=size&&map.get(maxHeap[child+1])<map.get(maxHeap[child])){
                child++;
            }
            if(map.get(temp)>map.get(maxHeap[child])){
                maxHeap[parent] = maxHeap[child];
                parent = child;
                child = 2*parent;
                continue;
            }else{
                break;
            }
        }
        maxHeap[parent] = temp;
    }
}
